// OD牛客网算法题,中秋节分月饼
// https://blog.csdn.net/whr19970424/article/details/121054029
// 中秋节，公司分月饼，m个员工，买了n个月饼，m<=n，每个员工至少分1个月饼，但可以分多个，
// 单人份到最多月饼的个数为Max1，单人分到第二多月饼的个数是Max2，Max1-Max2<=3,。
// 单人分到第n-1多月饼的个数是Max(n-1)，单人分到第n多月饼的个数是Max(n)，Max(n-1)-Max(n)<=3。
// 请问有多少种分月饼的方法
// 思路：先将m个人每个人分一个，这时，总月饼数是n-m
// 假设第一个人最少分k个，第二个人范围就是[k,
// k+3]，推而广之，这也是唯一可以利用的条件。
// 我们可以把3个人分的情况进行如下的分析：
// 第一个人最少分0个（事先已经分配了一个），那么剩下两个人有n-2个月饼可分，
//此时，如果第二个人分k个，第三个人就是n-2-k个，如果n-2-k <=
// k+3，那么这种情况就是成立的；
// 第一个人分1个，剩下两个人分n-2-1个
// 同样的，四个人的情况可以分为第一个人和后三个人，后三个人又可以分为第一个人和后两个人

#include <bits/stdc++.h>
using namespace std;

#define DEBUG_
#ifdef DEBUG_
#define PF(...) printf(__VA_ARGS__)
#define FRE(x)                    \
  freopen("d:/oj/" #x ".in", "r", \
          stdin)  //,freopen("d:/oj/"#x".out","w",stdout)
#define FREC fclose(stdin), fclose(stdout);
#else
#define PF(...)
#define FRE(x)
#define FREC
#endif

// got 表示分到月饼最少的那个人得到的月饼数
void dfsDispatch(int nPeople, int nMoon, int nMin, vector<int>& path,
                 vector<vector<int>>& ans) {
  if (nMoon <= 0 || nPeople <= 0) {
    return;
  }
  //人数为1
  if (nPeople == 1) {
    if (nMoon >= nMin && nMoon <= nMin + 3) {
      path.push_back(nMoon);
      ans.push_back(path);
      path.pop_back();
    }
    return;
  }
  //大于2的情况
  for (int got = nMin; got <= nMin + 3; got++) {
    path.push_back(got);
    dfsDispatch(nPeople - 1, nMoon - got, got, path, ans);
    path.pop_back();
  }
}

int moon_cake_example(int nPeople, int nMoon) {
  nMoon -= nPeople;  //每人至少一个月饼
  vector<int> path;
  vector<vector<int>> ans;
  for (int got = 0; got <= nMoon; got++) {
    path.push_back(got);
    dfsDispatch(nPeople - 1, nMoon - got, got, path, ans);
    path.pop_back();
  }
  for (auto vt : ans) {
    for (auto v : vt) {
      PF("%d,", v);
    }
    PF("\n");
  }
  PF("%d=====\n", ans.size());
  return ans.size();
}

int main() {
  int person = 3;
  int cake = 15;
  PF("person=%d, cake=%d,\n", person, cake);
  moon_cake_example(person, cake);
  PF("\n");
  return 0;
}
